
public class Tp2_Ej1_Main {

	public static void main(String[] args) {
		String nombreArchivo = "Tp2";
		
		String archivoEntrada = ".\\resources\\" + nombreArchivo + "Ej1.in";
		String archivoSalida = ".\\resources\\" + nombreArchivo + "Ej1.out";
		String archivoTiempos = ".\\resources\\" + nombreArchivo + "Ej1.time";
		
		algoritmo(archivoEntrada, archivoSalida, archivoTiempos);
	}
	
	private static void algoritmo(String archivoEntrada, String archivoSalida, String archivoTiempos) {
		FileParser fp = new FileParser(archivoEntrada);
		FileWriter fw = new FileWriter(archivoSalida);
		FileWriter fwTiempos = new FileWriter(archivoTiempos);
		
//		crearCaso(archivoEntrada);
		int cantidadRepeticiones=5;
		long minMedicion=0;
		int res = 0;
		
		while (!fp.getLine().trim().equals("-1")) {
			Parametros instancia = parsearInstancia(fp);
			for (int rep=0 ;rep<cantidadRepeticiones;rep++) {
				long tiempoInicio = System.nanoTime();
				res = minimosPasos(instancia);
				long totalTiempo = System.nanoTime()- tiempoInicio;
				minMedicion+=totalTiempo;
			}
			minMedicion /= cantidadRepeticiones;
			fwTiempos.writeLine(instancia.getcantElementos() + " " + String.valueOf(minMedicion));
			System.out.println("El resultado de la instancia es: " + res);
			fw.writeLine(String.valueOf(res));
		}
		
		fw.closeFile();
		fp.closeFile();
		fwTiempos.closeFile();
	}
	
	
	private static void crearMejorCaso(String archivoEntrada){
		FileWriter fw = new FileWriter(archivoEntrada);
		String texto= "";
		for (int cant=100;cant<=200;cant++){
			texto += cant + " ";
			for (int i=1;i<=cant;i++){
				texto += i + " ";
			}
		 	fw.writeLine(texto);
		 	texto="";
		}
		fw.writeLine("-1");
		fw.closeFile();
	}
	
	private static void crearPeorCaso(String archivoEntrada){
		FileWriter fw = new FileWriter(archivoEntrada);
		String texto= "";
		for (int cant=100;cant<=200;cant++){
			texto += cant + " ";
			for (int i=cant;i>=1;i--){
				texto += i + " ";
			}
		 	fw.writeLine(texto);
		 	texto="";
		}
		fw.writeLine("-1");
		fw.closeFile();
	}
	
	
	
	
	
	
	
	
	
	private static int minimosPasos(Parametros e) {
		int n 							= e.getcantElementos();
		int secuencia[] 				= e.getElementos();
		int longitud_creciente[] 		= new int[n]; 	// vector donde guardo la longitud de la secuencia creciente 
		int longitud_decreciente[] 		= new int[n]; 	// vector donde guardo la longitud de la secuencia decreciente

		int indice_creciente			= 0;			// variable para guardar el indice maximo para la secuencia creciente
		int indice_decreciente			= n - 1;		// variable para guardar el indice maximo para la secuencia decreciente
		int secuenciaParcialMasLargaCreciente	= 0; 			// variable para calculo de maximos y minimos
		int secuenciaParcialMasLargaDecreciente = 0; 			// variable para calculo de maximos y minimos
		
		//completo los vectores con 1 en todas sus posiciones. Ya que cada uno tomados como una secuencia de 1 elemento tienen longitud de 1.
		for (int i = 0 ; i<n ; i++){
			longitud_creciente[i] = 1;
			longitud_decreciente[i] = 1;
		}																	
		//o(n)
//INICIO ========================================================================= PRIMERA PARTE DEL ALGORITMO. 
//INICIO ========================================================================= BUSQUEDA DE SECUENCIAS CRECIENTES Y DECRECIENTES MAXIMAS 
		// busco las secuencias crecientes y decrecientes mas largas
		for (int i = 0 ; i<n ; i++){
			for (int j = 0 ; j<=i ; j++){
				//-------------------------------------------------------------------- secuencia creciente
				if (secuencia[j]<secuencia[i]){ 										// pregunta si el elemento de la izquierda es menor que el mismo 
					if(longitud_creciente[i]<=longitud_creciente[j]){ 					// pregunta si la longitud alcanzada hasta ese momento es menor que la longitud del elemento de la izquierda + 1
						longitud_creciente[i] = longitud_creciente[j] + 1; 				// si es menor o igual entonces tomo la longitud de ese elemento + 1 
						if (longitud_creciente[i] > secuenciaParcialMasLargaCreciente){								// busco el MENOR indice del elemento maximo de la secuencia creciente (explicar con un grafico)
							indice_creciente = i;										// lo guardo
							secuenciaParcialMasLargaCreciente = longitud_creciente[i];								// seteo el nuevo aux, que me sirve para ir viendo cual es el MENOR indice
						}
					}
				}	
				//-------------------------------------------------------------------- secuencia decreciente
				if (secuencia[n-j-1]<secuencia[n-i-1]){									// hago lo mismo pero de atras para adelante en el vector
					if(longitud_decreciente[n-i-1]<=longitud_decreciente[n-j-1]){
						longitud_decreciente[n-i-1] = longitud_decreciente[n-j-1] + 1;
						if (longitud_decreciente[n-i-1] > secuenciaParcialMasLargaDecreciente){						// busco el MAYOR indice del elemento maximo de la secuencia creciente (explicar con un grafico)
							indice_decreciente = n-i-1;
							secuenciaParcialMasLargaDecreciente = longitud_decreciente[n-i-1];
						}

					}
				}
			}
		}
//FIN ========================================================================= PRIMERA PARTE DEL ALGORITMO. 
//FIN ========================================================================= BUSQUEDA DE SECUENCIAS CRECIENTES Y DECRECIENTES MAXIMAS 

		
//INICIO ========================================================================= SEGUNDA PARTE DEL ALGORITMO. 
//INICIO ======================================================================== DEPENDIENDO DE LAS SECUENCIAS ENCONTRADAS ANTERIORMENTE 
//INICIO ======================================================================== BUSCO SECUENCIAS CRECIENTES/DECRECIENTES MAS CORTAS 
		
		if (longitud_creciente[indice_creciente] > longitud_decreciente[indice_decreciente]){ 	// esto indica si la secuencia mas larga es creciente o decreciente.
																								// dependiendo de eso el algoritmo toma 2 caminos
			// busco la decreciente hasta ese numero
			secuenciaParcialMasLargaDecreciente=0;
			for (int i = 0 ; i<n ; i++){
				longitud_decreciente[i] = 1;
			}
			for (int i = 0 ; i<=indice_creciente  ; i++){
				for (int j = 0 ; j<=i ; j++){
						
					if (secuencia[n-j-1]<secuencia[n-i-1]){									// hago lo mismo pero de atras para adelante en el vector
						if(longitud_decreciente[n-i-1]<=longitud_decreciente[n-j-1]){
							longitud_decreciente[n-i-1] = longitud_decreciente[n-j-1] + 1;
							if (longitud_decreciente[n-i-1] > secuenciaParcialMasLargaDecreciente){							// busco el MAYOR indice del elemento maximo de la secuencia creciente (explicar con un grafico)
								indice_decreciente = n-i-1;
								secuenciaParcialMasLargaDecreciente = longitud_decreciente[n-i-1];
							}
						}
					}
				}
			}
			// a esta altura del algoritmo estaria contando 2 veces el mismo elemento por eso disminuyo en 1 la longitud
			longitud_decreciente[indice_decreciente]--;
		}
		else{
			//busco la creciente hasta ese numero de indice.
			secuenciaParcialMasLargaCreciente=0;
				for (int i = 0 ; i<n ; i++){
					longitud_creciente[i] = 1;
				}
				for (int i = 0 ; i<=indice_decreciente ; i++){
					for (int j = 0 ; j<=i ; j++){
						if (secuencia[j]<secuencia[i]){ 							// pregunta si el elemento de la izquierda es menor que el mismo 
							if(longitud_creciente[i]<=longitud_creciente[j]){ 		// pregunta si la longitud alcanzada hasta ese momento es menor que la longitud del elemento de la izquierda + 1
								longitud_creciente[i] = longitud_creciente[j] + 1; 	// si es menor o igual entonces tomo la longitud de ese elemento + 1 
								if (longitud_creciente[i] > secuenciaParcialMasLargaCreciente){					// busco el MENOR indice del elemento maximo de la secuencia creciente (explicar con un grafico)
									indice_creciente = i;							// lo guardo
									secuenciaParcialMasLargaCreciente = longitud_creciente[i];					// seteo el nuevo aux, que me sirve para ir viendo cual es el MENOR indice
								}
							}
						}
					}
				}
				// a esta altura del algoritmo estaria contando 2 veces el mismo elemento por eso disminuyo en 1 la longitud
				longitud_creciente[indice_creciente]--;
		}

		return (n - longitud_creciente[indice_creciente] - longitud_decreciente[indice_decreciente]) ;
	}
	
	private static Parametros parsearInstancia(FileParser fp) {
		Parametros res = new Parametros();
		String[] str = fp.getLine().trim().replaceAll("\\s+", " ").split("\\s");
		res.setcantElementos(Integer.parseInt(str[0]));
		
		int[] elementos = new int[res.getcantElementos()];
		int i = 1;
		int j = 0;
		
		while (j <= res.getcantElementos()-1) {
			elementos[j]=(Integer.parseInt(str[i]));
			i++;
			j++;
		}
		
		res.setElementos(res.getcantElementos(),elementos);
		fp.nextLine();
		
		return res;
	}
	
}
